package com.leetcode.No0801;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 使序列递增的最小交换次数
 * 对 Solution4 中的dp进行空间优化，
 * 结果没想到对时间也有影响，从18ms降到了3ms，优化了很多！
 * 但是空间反而多占用了一点点，从52.4M提高到53.3M，不过跟时间比起来微不足道
 * @author: Wang Zhihua
 * @date: 2022-10-10
 */
public class Solution5 {
    public int minSwap(int[] nums1, int[] nums2) {
        int len = nums1.length;

        int a = 0, b = 1;

        for (int i = 1; i < len; ++i) {
            int preA = a, preB = b;
            boolean x = (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]);
            boolean y = (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]);
            if (x && y) {
                a = Math.min(preA, preB);
                b = a + 1;
            } else if (x) {
                a = preA;
                b = preB + 1;
            } else {
                a = preB;
                b = preA + 1;
            }
        }

        return Math.min(a, b);
    }

    @Test
    public void test1() {

        int[] nums1 = new int[]{1,3,5,4};
        int[] nums2 = new int[]{1,2,3,7};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,3,5,8,9};
        nums2 = new int[]{2,1,4,6,9};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,4,4,5, 9};
        nums2 = new int[]{0,1,6,8,10};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,2,5,8,9,10,12,14,18,19,20,20,24,27,28,31,33,34,36,38};
        nums2 = new int[]{1,2,5,7,8, 9,11,17,15,16,19,21,28,29,30,31,33,34,38,39};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{3,3,8,9,10};
        nums2 = new int[]{1,7,4,6,8};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{2,3,2,5,6};
        nums2 = new int[]{0,1,4,4,5};
//        System.out.println(minSwap(nums1, nums2));

        nums1 = new int[]{0,3,2,4,6,11,12,15,16,17};
        nums2 = new int[]{1,1,5,7,8, 9,12,13,14,18};
        System.out.println(minSwap(nums1, nums2));
    }
}
